package algocasts;

public class P136_ReverseWordsInAString {
    private void reverse(char[] str, int i, int j) {
        for (; i < j; i++, j--) {
            char tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
        }
    }

    // Time: O(n)  Time: O(n)
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;
        char[] str = s.toCharArray();
        int p = 0, q = 0, end = s.length() - 1;
        while (end >= 0 && str[end] == ' ') end--;
        while (q <= end) {
            int start = p;
            while (q <= end && str[q] == ' ') q++;
            while (q <= end && str[q] != ' ') str[p++] = str[q++];
            reverse(str, start, p - 1);
            if (q <= end) str[p++] = ' ';
        }
        reverse(str, 0, p - 1);
        return new String(str, 0, p);
    }
}
